package Algorithm.backTracking;

import java.util.Arrays;

/**
 * 698. 划分为k个相等的子集 https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/
 * 题目简述：给定一个整数数组nums和一个正整数k，找出是否有可能把这个数组分成k个非空子集，其总和都相等。
 */
public class CanPartitionKSubsets {

    public static void main(String[] args) {
        //验证剪枝：if (nowSubSum == 0) return false;
        new CanPartitionKSubsets().canPartitionKSubsets(new int[]{3,4,4,9,1,9}, 3);
    }

    /**
     * 思路：回溯算法。这是非连续分割问题，结合了子集，但是不同的是可以有重复的子集。主要思路就是递归的在剩余元素中寻找和为subSum的子集。
     * 首先计算目标子集总和subSum，将数组进行排序，并初始化一个已使用标记数组used
     * 回溯递归函数参数：（已找到的子集数ck，当前子集和nowSubSum，数组nums，[0, idx]和已使用标记used构成的下一步路径选择列表）
     * 回溯递归函数体：1.若找到了k个和为subSum的子集，则必然所有元素都刚好用到了，直接返回true。
     *                 若nowSubSum==subSum，说明找到了一个和为subSum的子集。将nowSubSum归零ck增1然后递归继续在剩余元素中寻找子集
     *              2.倒序遍历当前选择列表[0, idx]。剪枝1：已使用数据略过。剪枝2：若nowSubSum + nums[i]已经大于subSum，则略过nums[i]继续向后遍历同层其他选择寻找更小元素。
     *                 然后递归下一步选择列表[0, idx-1]，完毕后撤销上一步选择，继续遍历同层其他选择
     */
    int subSum = 0;//目标子集总和
    int k;
    public boolean canPartitionKSubsets(int[] nums, int k) {
        this.k = k;
        int sum = 0;
        for(int num : nums) {
            sum += num;
        }
        if(sum % k != 0) return false;//若总和就不可能均分为k份，则直接返回false
        subSum = sum / k;
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        return backTracing(0, 0, nums, nums.length-1, used);
    }

    /**
     * 1. 在剩余元素中寻找一个和为subSum的子集。
     * 2. 找到后将参数归零继续在剩余元素中寻找，若找到k个则返回true
     *
     * 若最终遍历完还是没有return true，即没有找到k个和为subSum的子集，则return false;
     */
    public boolean backTracing(int ck, int nowSubSum, int[] nums, int idx, boolean[] used) {
        //若找到了k个和为subSum的子集，则必然所有元素都刚好用到了，直接返回true
        if (ck == k) return true;
        //若nowSubSum==subSum，说明找到了一个和为subSum的子集。将nowSubSum归零ck增1然后递归继续在剩余元素中寻找子集
        if (nowSubSum == subSum) return backTracing(ck+1, 0, nums, nums.length-1, used);

        //路径选择列表 子集属于组合，可进行顺序性剪枝
        for(int i = idx;i >= 0 ;i--) {
            //可行性剪枝：已使用数据略过
            if(!used[i]) {
                //剪枝：若nowSubSum + nums[i]已经大于subSum，则略过nums[i]继续向后遍历同层其他选择寻找更小元素
                if (nowSubSum + nums[i] > subSum) continue;
                used[i] = true;
                if (backTracing(ck, nowSubSum + nums[i], nums, i-1, used)) return true;
                used[i] = false;
                //下面这个剪枝有些难理解，不用这个剪枝也能过
                //剪枝：此时若nowSubSum=0，则说明此层选择是在选子集中的第一个元素 即剩余元素中的最大值，并且没有在剩余元素中找到能与这个元素进行组合的元素集。
                //      那么是不是可以考虑将它与已构好的子集中的元素进行替换呢？
                //          1.若替换出的是一个相同值元素，那还是一样的
                //          2.由于每次构造子集是从大到小选择 尽量选择剩余元素中较大元素进行构造，那么前面构造的子集中必然没有一个子集中会存在几个较小元素之和为它，不然它在前面的子集中就已经被选用了，轮不到后面的小元素
                //      因此它没办法再参与构成一个子集了，直接返回false
                if (nowSubSum == 0) return false;
            }
        }
        return false;
    }
}
